package com.sise.Backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *      面试题 08.08. 有重复字符串的排列组合
 *      有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。
 *
 *      示例1:
 *      输入：S = "qqe"
 *      输出：["eqq","qeq","qqe"]
 */
public class _interview_08_08_permutation {

    public static void main(String[] args) {
        System.out.println("总结果："+Arrays.toString(permutation("qqqa")));
    }

    static public String[] permutation(String S) {

        List<String> list = new ArrayList<>();
        char[] arr = S.toCharArray();
        // 对其字符串进行排序 是关键，在后续才可以 比较相邻元素
        Arrays.sort(arr);
        boolean[] used = new boolean[arr.length];
        dfs(list, new StringBuilder(), used, arr);

        String[] res = new String[list.size()];
        for (int i = 0; i < res.length; i++)
            res[i] = list.get(i);

        return res;
    }

    static public void dfs(List<String> res, StringBuilder sb, boolean[] used, char[] arr) {

        if (sb.length() == arr.length) {
            res.add(sb.toString());
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (!used[i]) {
                // i > 0 是为了 arr[i - 1] 不为负数做准备
                // arr[i] == arr[i - 1] 表示相邻数字，例如 abb

                // 我们只允许"b1b2b3"或"b3b2b1"其中一种方式存在；以只允许"b1b2b3"存在为例；
                // 当我们遍历到b2时，假如b1已经加入排序，我们就可以将b2也加入排序，否则跳过；
                // 当我们遍历到b3时，假如b2已经加入排序，我们就可以将b3也加入排序，否则跳过；
                // !used[i - 1] => used[i-1] = true => i-1 位置被使用过，也就是说取前者，因为这里的 continue 是跳过的意思(待验证)
                // 这里的 used[] 代表的是 'aab' 的索引位置， arr[] 代表的是 目标值，要区分开来
                if (i > 0 && arr[i] == arr[i - 1] && used[i - 1] == false){
                    continue;
                } else {
                    sb.append(arr[i]);
                    used[i] = true;
                    dfs(res, sb, used, arr);
                    used[i] = false;
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
    }
}
